package com.leetcode.根据数据结构分类.并查集;

/**
 * @author: ZhouBert
 * @date: 2021/1/6
 * @description: 990. 等式方程的可满足性
 * https://leetcode-cn.com/problems/satisfiability-of-equality-equations/
 * 并查集的典型应用
 * （real talk 在刚学完 Union Find 以后还不知道如何能将其应用到实际情况中）
 */
public class B_990_等式方程的可满足性 {


	/**
	 * 如果抽象成 UnionFind
	 * 那么：== :theSame();!=:!theSame() 或者是 添加到 并查集中
	 * 跑了很多测试用例以后，发现还有个bug不好解决:
	 * 对于已经添加到并查集的元素，进行再次判断，eg."e==d", "e==a", "f!=d", "b!=c", "a==b"
	 *
	 * @param equations
	 * @return
	 */
	public boolean equationsPossible_fail(String[] equations) {
		//并查集结构基础//由于初始时都为0，那么不让 0 的位置有意义
		int[] parents = new int[27];

		for (int i = 0; i < equations.length; i++) {
			//获取第一个 参数的索引
			int index1 = equations[i].charAt(0) - 'a' + 1;
			//获取第二个 参数的索引
			int index2 = equations[i].charAt(3) - 'a' + 1;


			if (equations[i].charAt(1) == '!') {
				if (index1 == index2) {
					return false;
				}
				//如果是 !=
				if (parents[index1] == 0 && parents[index2] == 0) {
					//1.都没有加入到 union find
					parents[index1] = index1;
					parents[index2] = index2;
				} else if (parents[index1] == 0 && parents[index2] != 0) {
					//2.index1 没有加入 union find,但是 index2 已经加入了
					parents[index1] = index1;
				} else if (parents[index2] == 0 && parents[index1] != 0) {

					parents[index2] = index2;
				} else {
					//都已经加进去了
					//--> 进行判断
					if (isSame(parents, index1, index2)) {
						return false;
					}
				}
			} else {
				if (index1 == index2) {
					//如果相等，就没有意义
					continue;
				}
				// ==
				if (parents[index1] == 0 && parents[index2] == 0) {
					//1.都没有加入到 union find + 设置为同一个
					parents[index1] = index1;
					parents[index2] = index1;
				} else if (parents[index1] == 0 && parents[index2] != 0) {
					//2.index1 没有加入 union find,但是 index2 已经加入了
					//--> 让 index1 嫁接到 index2 中
					parents[index1] = index1;
					union(parents, index1, index2);
				} else if (parents[index2] == 0 && parents[index1] != 0) {
					parents[index2] = index2;
					union(parents, index2, index1);
				} else {
					//都已经加进去了
					//--> 进行判断
//					if (!isSame(parents, index1, index2)) {
//						return false;
//					}
					//如果已经做好了排序，一直 == 下去是不会出错的！那么只需要做 union 就好了
					union(parents, index1, index2);

				}
			}
		}

		return true;
	}

	/**
	 * 1.先将equations 进行排序，== 放在前面
	 * 2.然后再通过上面的进行判断
	 * 这个算法是可行的！终于做到了 击败 100%！
	 * @param equations
	 * @return
	 */
	public boolean equationsPossible(String[] equations) {
		int begin = 0;
		int end = equations.length - 1;
		while (begin < end) {
			if (equations[begin].charAt(1) == '!') {
				while (equations[end].charAt(1) != '=' && begin < end) {
					end--;
				}
				if (begin < end) {
					String temp = equations[begin];
					equations[begin] = equations[end];
					equations[end] = temp;
				}
			} else {
				begin++;
			}
		}
		return equationsPossible_fail(equations);
	}

	/**
	 * 由于一共 26 个，所以 QuickFind 也没问题
	 *
	 * @param parents
	 * @param index
	 * @return
	 */
	private int find(int[] parents, int index) {
		return parents[index];
	}

	/**
	 * 判断两个元素是否相等
	 * 如果
	 *
	 * @param parents
	 * @param index1
	 * @param index2
	 * @return
	 */
	private boolean isSame(int[] parents, int index1, int index2) {

		return find(parents, index1) == find(parents, index2);


//		int p1 = find(parents, index1);
//		int p2 = find(parents, index2);
//		if (p1 == p2) {
//			return true;
//		}
//		if (p1 != index1 && p2 != index2) {
//			return false;
//		}
//		if (p1 == index1) {
//			union(parents, index1, index2);
//		} else if (p2 == index2) {
//			union(parents, index2, index1);
//		}
//
//		return true;
	}

	/**
	 * 将 index1 嫁接到 index2
	 * 前提条件是：index1 和 index2 都在 UnionFind 里面
	 *
	 * @param parents
	 * @param index1
	 * @param index2
	 */
	private void union(int[] parents, int index1, int index2) {
		int p1 = find(parents, index1);
		int p2 = find(parents, index2);
		if (p1 == p2) {
			return;
		}
		for (int i = 1; i < parents.length; i++) {
			if (parents[i] == p1) {
				parents[i] = p2;
			}
		}
	}


	public static void main(String[] args) {
		String[] equations = new String[]{"a==b", "b!=a"};
		equations = new String[]{"b==a", "a==b"};
		equations = new String[]{"a==b", "b==c", "a==c"};
		//["c==c","f!=a","f==b","b==c"
		equations = new String[]{"b==b", "b==e", "e==c", "d!=e"};
		equations = new String[]{"c==c", "f!=a", "f==b", "b==c"};
		equations = new String[]{"e==d", "e==a", "f!=d", "b!=c", "a==b"};
		equations = new String[]{"b==d", "c==a", "h==a", "d==d", "a==b", "h!=k", "i==h"};
		B_990_等式方程的可满足性 action = new B_990_等式方程的可满足性();
		boolean res = action.equationsPossible(equations);
		System.out.println("res = " + res);
	}
}
